import java.util.Arrays;

/**
    1. 基础结构与初始化
    初始化流程：
    构造方法创建初始容量为10的数组
    initElem() 将输入数组拷贝到 elem 中，不建立堆结构
    注意：此时数组只是普通数组，尚未形成堆结构

 * */
public class TestHeap {
    public int[] elem;     // 存储堆元素的数组
    public int usedSize;   // 堆中当前有效元素数量

    // 构造方法
    public TestHeap() {
        this.elem = new int[10];  // 初始容量为10
    }

    // 初始化数组（未建堆）
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;  // 更新有效元素计数
        }
    }

    // 建堆操作
    public void createHeap() {
        // 从最后一个非叶子节点开始向前遍历
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            siftDown(parent, usedSize);  // 向下调整
        }
    }

    // 向下调整
    // 时间复杂度： O(logN)
    private void siftDown(int parent, int usedSize) {
        int child = 2*parent+1; // 左孩子
        //至少有左孩子
        while (child < usedSize) { // usedSize是堆中当前有效元素，堆边界，确保只调整堆内元素0
            //1.比较左右孩子最大值
            if(child+1 < usedSize && elem[child] < elem[child+1]) {
                child++;
            }
            //走到这里 child一定是左右孩子的最大值的下标
            if(elem[child] > elem[parent]) {
                swap(elem,parent,child);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, elem.length*2);  // 扩容
        }
        elem[usedSize] = val;  // 新元素放末尾
        // usedSize 是当前堆的末尾位置（新元素插入点）,新元素插入后还未增加 usedSize，所以 usedSize 就是新元素下标
        // 新元素在堆底，需要向上比较父节点
        siftUp(usedSize);      // 向上调整
        usedSize++;            // 更新大小
    }

    private void siftUp(int child) {
        int parent = (child - 1) / 2;  // 计算父节点
        while (parent >= 0) {
            if (elem[child] > elem[parent]) {
                swap(elem, parent, child);  // 交换
                child = parent;             // 上移子指针
                parent = (child - 1) / 2;   // 更新父节点
            } else {
                break;  // 调整完成
            }
        }
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    /*
    核心逻辑：
        首尾交换：堆顶（最大值）与最后元素交换
        逻辑删除：usedSize-- 移除尾部（原堆顶）
        向下调整：从根节点开始维护堆性质
        注意：交换后 usedSize-- 再调整，确保被删除元素不参与调整
    * */
    public void poll() {
        if (isEmpty()) return;
        swap(elem, 0, usedSize-1);  // 交换首尾
        usedSize--;                  // 删除尾部（原堆顶）
        siftDown(0, usedSize);       // 新堆顶向下调整
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    /*
    核心逻辑：
        将最大值(堆顶)交换到数组末尾
        剩余部分重新调整为大顶堆
        重复直到堆大小为1
    为什么 end > 0：
        当 end=1 时，交换后排序完成
    时间复杂度：O(NlogN)
    结果特点：
        升序排列（从小到大），但破坏原堆结构
    * */
    public void heapSort() {
        int end = usedSize-1; // 最后元素下标
        while (end > 0) {     // 直到堆剩1元素
            swap(elem,0,end);// 堆顶(最大值)移到最后
            siftDown(0,end); // 调整剩余堆
            end--;                  // 缩小堆范围
        }
    }

}
